package leetCode;

/**
 * LCR 008. 长度最小的子数组
 * https://leetcode.cn/problems/2VG8Kg/description/
 */
class Solution1 {
    public static void main(String[] args) {
        minSubArrayLen(7, new int[]{2,3,1,2,4,3});
    }
    public static int minSubArrayLen(int target, int[] nums) {
        int n = nums.length, len = Integer.MAX_VALUE;//nums数组的长度，长度最小子串
        int sum = 0;//子串和
        for(int left = 0, right = 0; right < n; right++) {
            //进窗口,right会自己++
            sum += nums[right];
            //判断
            while(sum >= target) {
                //更新len和sum的值，出窗口
                len = Math.min(len, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }
    //自己的版本，比较耗时
    public int minSubArrayLen1(int target, int[] nums) {
        int left = 0, right = 0;
        int len = Integer.MAX_VALUE;//子长度和子长度之间的和
        int n = nums.length;
        while(left <= right) {
            int sum = 0;
            for(int i = left; i <= right; i++) {
                sum += nums[i];
            }
            //left到right之间的长度算出来了，target和sum作比较
            if(sum < target) {
                if(right < n - 1) {
                    //进窗口
                    right++;
                } else break;
            } else {
                if(left <= right) {
                    //更新长度
                    len = Math.min(len, right - left + 1);
                }
                //出窗口 sum >= target
                left++;
            }
        }
        if(len == Integer.MAX_VALUE) return 0;
        return len;
    }
}